#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
int solution(std::string dna1, std::string dna2) {
    // Please write your code here
    int m = dna1.size();
    int n = dna2.size();
    std::vector<std::vector<int>> step(m + 1, std::vector<int>(n + 1, 0));
    //step[i][j]表示dna1的前i个字符变为dna2的前j个字符需要的步数
    //dna1[i]==dna2[j],step[i][j]=step[i-1][j-1]
    //dna1[i]!=dna2[j],step[i][j]=min(step[i-1][j],min(step[i][j-1],step[i-1][j-1]))+1
    int i = 0, j = 0;
    for (i = 1; i <= m; i++)
    {
        step[i][0] = i;
        for (j = 1; j <= n; j++)
        {
            step[0][j] = j;
            if (dna1[i - 1] == dna2[j - 1])
            {
                step[i][j] = step[i - 1][j - 1];
            }
            else
            {
                step[i][j] = std::min(step[i - 1][j], std::min(step[i][j - 1], step[i - 1][j - 1])) + 1;
            }
        }
    }
    return step[m][n];
}

void sol(std::vector<int>& num, int sum, int pos, int& count)
{
    if (pos == num.size())
    {
        if (sum % 2 == 0)
        {
            count++;
        }
        return;
    }
    std::vector<int> temp;
    int flag = num[pos];
    while (flag)
    {
        temp.push_back(flag % 10);
        flag /= 10;
    }
    for (int i = 0; i < temp.size(); i++)
    {
        sol(num, sum + temp[i], pos + 1, count);
    }
}

int solution1(std::vector<int> numbers) {
    // Please write your code here
    int count = 0;
    sol(numbers, 0, 0, count);
    return count;
}

std::string solution2(const std::string& s) 
{
    // write code here
    std::string ret;
    std::string temp;
    int i=s.size()-1;
    auto it=s.find('.');
    if(it!=std::string::npos)
    {
        i=it;
        while(i<s.size())
        {
            temp.push_back(s[i]);
            i++;
        }
        i=it-1;
    }
    
    int count=0;
    while(i>=0)
    {
        if(count==3)
        {
            ret.push_back(',');
            count=0;
        }
        ret.push_back(s[i]);
        count++;
        i--;
    }
    std::reverse(ret.begin(),ret.end());
    i=0;
    while(ret[i]==','||ret[i]=='0')
    {
        ret.erase(i,1);
        i=0;
    }

    return ret+temp;
}

int main() {
    //  You can add more test cases here
    std::cout << (solution1({ 123, 456, 789 }) == 14) << std::endl;
    std::cout << (solution1({ 123456789 }) == 4) << std::endl;
    std::cout << (solution1({ 14329, 7568 }) == 10) << std::endl;

    std::cout << (solution("AGCTTAGC", "AGCTAGCT") == 2) << std::endl;
    std::cout << (solution("AGCCGAGC", "GCTAGCT") == 4) << std::endl;
    
    std::cout << solution2("1294512.12412") << std::endl;
    std::cout << solution2("0000123456789.99") << std::endl;
    std::cout << solution2("987654321") << std::endl;
    return 0;
}